{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Stone Game VII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming #game-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划 #博弈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: stoneGameVII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #石子游戏 VII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，<strong>爱丽丝先开始</strong> 。</p>\n",
    "\n",
    "<p>有 <code>n</code> 块石子排成一排。每个玩家的回合中，可以从行中 <strong>移除</strong> 最左边的石头或最右边的石头，并获得与该行中剩余石头值之 <strong>和</strong> 相等的得分。当没有石头可移除时，得分较高者获胜。</p>\n",
    "\n",
    "<p>鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 <strong>减小得分的差值</strong> 。爱丽丝的目标是最大限度地 <strong>扩大得分的差值</strong> 。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>stones</code> ，其中 <code>stones[i]</code> 表示 <strong>从左边开始</strong> 的第 <code>i</code> 个石头的值，如果爱丽丝和鲍勃都 <strong>发挥出最佳水平</strong> ，请返回他们 <strong>得分的差值</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stones = [5,3,1,4,2]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>\n",
    "- 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5,3,1,4] 。\n",
    "- 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3,1,4] 。\n",
    "- 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1,4] 。\n",
    "- 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。\n",
    "- 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。\n",
    "得分的差值 18 - 12 = 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stones = [7,90,5,1,100,10,10,2]\n",
    "<strong>输出：</strong>122</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == stones.length</code></li>\n",
    "\t<li><code>2 <= n <= 1000</code></li>\n",
    "\t<li><code>1 <= stones[i] <= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [stone-game-vii](https://leetcode.cn/problems/stone-game-vii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [stone-game-vii](https://leetcode.cn/problems/stone-game-vii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,3,1,4,2]', '[7,90,5,1,100,10,10,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        presum = [0]\n",
    "        for s in stones:\n",
    "            presum.append(presum[-1] + s)\n",
    "        n = len(stones)\n",
    "        dp = [0]*n\n",
    "        for l in range(1, n):\n",
    "            ndp = []\n",
    "            for i in range(n - l):\n",
    "\n",
    "                ndp.append(max(presum[i + l] - presum[i] - dp[i], presum[i+l+1] - presum[i+1] - dp[i+1]))\n",
    "            dp = ndp\n",
    "        return ndp[0]\n",
    "\n",
    "        # def dfs(l, r):\n",
    "        #     if l == r:\n",
    "        #         return 0\n",
    "        #     return max(presum[r] - presum[l] - dfs(l, r - 1), presum[r+1] - presum[l+1] - dfs(l+1, r))\n",
    "        # return dfs(0, len(stones) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        if not n & 1:\n",
    "            for i in range(n):\n",
    "                dp[i][i] = stones[i]\n",
    "        for L in range(2, n + 1):\n",
    "            for i in range(n - L + 1):\n",
    "                j = i + L - 1\n",
    "                if L & 1 == n & 1:\n",
    "                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i + 1][j] + stones[i], dp[i][j - 1] + stones[j])\n",
    "        return dp[0][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        if n & 1 == 0:\n",
    "            for i in range(n):\n",
    "                f[i][i] = stones[i]\n",
    "        for L in range(2, n + 1):\n",
    "            for i in range(n - L + 1):\n",
    "                j = i + L - 1\n",
    "                if L & 1 == n & 1:\n",
    "                    f[i][j] = max(f[i + 1][j], f[i][j - 1])\n",
    "                else:\n",
    "                    f[i][j] = min(f[i + 1][j] + stones[i], f[i][j - 1] + stones[j])\n",
    "        return f[0][-1]\n",
    "\n",
    "        # s = list(accumulate(stones, initial=0))\n",
    "        # n = len(stones)\n",
    "        # f = [[0] * n for _ in range(n)]\n",
    "        # for L in range(2, n + 1):\n",
    "        #     i, j = 0, L - 1\n",
    "        #     while j < n:\n",
    "        #         f[i][j] = max(s[j + 1] - s[i + 1] - f[i + 1][j], s[j] - s[i] - f[i][j - 1])\n",
    "        #         i += 1\n",
    "        #         j += 1\n",
    "        # return f[0][n - 1]\n",
    "\n",
    "        # s = list(accumulate(stones, initial=0))\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i == j:\n",
    "        #         return 0\n",
    "        #     return max(s[j + 1] - s[i + 1] - dfs(i + 1, j), s[j] - s[i] - dfs(i, j - 1))\n",
    "        # res = dfs(0, len(stones) - 1)\n",
    "        # del dfs\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        # 长度偶数\n",
    "        if not  n & 1:\n",
    "            for i in range(n):\n",
    "                dp[i][i] = stones[i]\n",
    "        \n",
    "        for L in range(2, n+1):\n",
    "            for i in range(n - L +1):\n",
    "                j = i + L - 1\n",
    "\n",
    "                if L & 1 == n & 1:\n",
    "                    dp[i][j] = max(dp[i][j-1], dp[i+1][j])\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i+1][j] + stones[i], dp[i][j-1] + stones[j])\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        t = n & 1\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        if t == 0:\n",
    "            for i in range(n):\n",
    "                dp[i][i] = stones[i]\n",
    "        for L in range(2, n + 1):\n",
    "            for i in range(n - L + 1):\n",
    "                j = i + L - 1\n",
    "                if L & 1 == t:\n",
    "                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i + 1][j] + stones[i], dp[i][j - 1] + stones[j])\n",
    "        return dp[0][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        if not n & 1:\n",
    "            for i in range(n):\n",
    "                dp[i][i] = stones[i]\n",
    "        for L in range(2, n + 1):\n",
    "            for i in range(n - L + 1):\n",
    "                j = i + L - 1\n",
    "                if L & 1 == n & 1:\n",
    "                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i + 1][j] + stones[i], dp[i][j - 1] + stones[j])\n",
    "        return dp[0][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        if not n & 1:\n",
    "            for i in range(n):\n",
    "                dp[i][i] = stones[i]\n",
    "        for L in range(2, n + 1):\n",
    "            for i in range(n - L + 1):\n",
    "                j = i + L - 1\n",
    "                if L & 1 == n & 1:\n",
    "                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i + 1][j] + stones[i], dp[i][j - 1] + stones[j])\n",
    "        return dp[0][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        N=len(stones)\n",
    "        dp=[[0 for m in range(N)] for n in range(N)]\n",
    "        if N%2==1:\n",
    "            for k in range(N):\n",
    "               dp[k][k]=0\n",
    "        else:\n",
    "            for k in range(N):\n",
    "                dp[k][k]=stones[k]\n",
    "\n",
    "        for p in range(1,N):\n",
    "            for q in range(N-p):\n",
    "                i=q\n",
    "                j=p+q\n",
    "                if (j-i+1)%2==N%2:\n",
    "                    dp[i][j]=max(dp[i+1][j],dp[i][j-1])\n",
    "                else:\n",
    "                    dp[i][j]=min(stones[i]+dp[i+1][j],stones[j]+dp[i][j-1])\n",
    "        return dp[0][N-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        if n %2 == 0:\n",
    "            for i in range(n):\n",
    "                dp[i][i] = stones[i]\n",
    "\n",
    "        for l in range(2, n+1):\n",
    "            for i in range(n-l+1):\n",
    "                j = i + l -1\n",
    "                if l & 1 == n & 1:\n",
    "                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i+1][j] + stones[i], dp[i][j-1] + stones[j])\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        N=len(stones)\n",
    "        dp=[[0 for m in range(N)] for n in range(N)]\n",
    "        if N%2==1:\n",
    "            for k in range(N):\n",
    "               dp[k][k]=0\n",
    "        else:\n",
    "            for k in range(N):\n",
    "                dp[k][k]=stones[k]\n",
    "\n",
    "        for p in range(1,N):\n",
    "            for q in range(N-p):\n",
    "                i=q\n",
    "                j=p+q\n",
    "                if (j-i+1)%2==N%2:\n",
    "                    dp[i][j]=max(dp[i+1][j],dp[i][j-1])\n",
    "                else:\n",
    "                    dp[i][j]=min(stones[i]+dp[i+1][j],stones[j]+dp[i][j-1])\n",
    "        return dp[0][N-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        N=len(stones)\n",
    "        dp=[[0 for m in range(N)] for n in range(N)]\n",
    "        if N%2==1:\n",
    "            for k in range(N):\n",
    "               dp[k][k]=0\n",
    "        else:\n",
    "            for k in range(N):\n",
    "                dp[k][k]=stones[k]\n",
    "\n",
    "        for p in range(1,N):\n",
    "            for q in range(N-p):\n",
    "                i=q\n",
    "                j=p+q\n",
    "                if (j-i+1)%2==N%2:\n",
    "                    dp[i][j]=max(dp[i+1][j],dp[i][j-1])\n",
    "                else:\n",
    "                    dp[i][j]=min(stones[i]+dp[i+1][j],stones[j]+dp[i][j-1])\n",
    "        return dp[0][N-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        N=len(stones)\n",
    "        dp=[[0 for m in range(N)] for n in range(N)]\n",
    "        if N%2==1:\n",
    "            for k in range(N):\n",
    "               dp[k][k]=0\n",
    "        else:\n",
    "            for k in range(N):\n",
    "                dp[k][k]=stones[k]\n",
    "\n",
    "        for p in range(1,N):\n",
    "            for q in range(N-p):\n",
    "                i=q\n",
    "                j=p+q\n",
    "                if (j-i+1)%2==N%2:\n",
    "                    dp[i][j]=max(dp[i+1][j],dp[i][j-1])\n",
    "                else:\n",
    "                    dp[i][j]=min(stones[i]+dp[i+1][j],stones[j]+dp[i][j-1])\n",
    "        return dp[0][N-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        N=len(stones)\n",
    "        dp=[[0 for m in range(N)] for n in range(N)]\n",
    "        if N%2==1:\n",
    "            for k in range(N):\n",
    "               dp[k][k]=0\n",
    "        else:\n",
    "            for k in range(N):\n",
    "                dp[k][k]=stones[k]\n",
    "\n",
    "        for p in range(1,N):\n",
    "            for q in range(N-p):\n",
    "                i=q\n",
    "                j=p+q\n",
    "                if (j-i+1)%2==N%2:\n",
    "                    dp[i][j]=max(dp[i+1][j],dp[i][j-1])\n",
    "                else:\n",
    "                    dp[i][j]=min(stones[i]+dp[i+1][j],stones[j]+dp[i][j-1])\n",
    "        return dp[0][N-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        N=len(stones)\n",
    "        dp=[[0 for m in range(N)] for n in range(N)]\n",
    "        if N%2==1:\n",
    "            for k in range(N):\n",
    "               dp[k][k]=0\n",
    "        else:\n",
    "            for k in range(N):\n",
    "                dp[k][k]=stones[k]\n",
    "\n",
    "        for p in range(1,N):\n",
    "            for q in range(N-p):\n",
    "                i=q\n",
    "                j=p+q\n",
    "                if (j-i+1)%2==N%2:\n",
    "                    dp[i][j]=max(dp[i+1][j],dp[i][j-1])\n",
    "                else:\n",
    "                    dp[i][j]=min(stones[i]+dp[i+1][j],stones[j]+dp[i][j-1])\n",
    "        return dp[0][N-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "\n",
    "        # 计算前缀和数列\n",
    "        prefix = [0]\n",
    "        now = 0\n",
    "        for s in stones:\n",
    "            now += s\n",
    "            prefix.append(now)\n",
    "\n",
    "        # print(\"前缀和:\", prefix)\n",
    "\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for l in range(1, n):\n",
    "            for i in range(n - l):\n",
    "                j = i + l\n",
    "\n",
    "                # 当剩下2个石头时\n",
    "                if l == 1:\n",
    "                    dp[i][j] = max(stones[i], stones[j])\n",
    "\n",
    "                # 当剩下3个及以上的石头时\n",
    "                else:\n",
    "                  \n",
    "                    dp[i][j] = max((prefix[j + 1] - prefix[i + 1]) - dp[i + 1][j],  \n",
    "                                   (prefix[j] - prefix[i]) - dp[i][j - 1])  \n",
    "\n",
    "        return dp[0][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        pres = list(accumulate(stones, initial=0))\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                dp[i][j] = max(pres[j + 1] - pres[i + 1] - dp[i + 1][j], pres[j] - pres[i] - dp[i][j - 1])\n",
    "\n",
    "        return dp[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        presum=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            presum[i]=stones[i-1]+presum[i-1]\n",
    "        dp=[[0]*n for _ in range(n)]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                l=presum[j+1]-presum[i+1]\n",
    "                r=presum[j]-presum[i]\n",
    "                dp[i][j]=max(l-dp[i+1][j],r-dp[i][j-1])\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        presum = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            presum[i] = presum[i - 1] + stones[i - 1]\n",
    "\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                l = presum[j + 1] - presum[i + 1]\n",
    "                r = presum[j] - presum[i]\n",
    "                dp[i][j] = max(l - dp[i + 1][j], r - dp[i][j - 1])\n",
    "        return dp[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        s = list(accumulate(stones, initial=0))\n",
    "        n = len(stones)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for L in range(2, n + 1):\n",
    "            i, j = 0, L - 1\n",
    "            while j < n:\n",
    "                f[i][j] = max(s[j + 1] - s[i + 1] - f[i + 1][j], s[j] - s[i] - f[i][j - 1])\n",
    "                i += 1\n",
    "                j += 1\n",
    "        return f[0][n - 1]\n",
    "\n",
    "        # s = list(accumulate(stones, initial=0))\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i == j:\n",
    "        #         return 0\n",
    "        #     return max(s[j + 1] - s[i + 1] - dfs(i + 1, j), s[j] - s[i] - dfs(i, j - 1))\n",
    "        # res = dfs(0, len(stones) - 1)\n",
    "        # del dfs\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            f[i + 1] = f[i] + stones[i]\n",
    "\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for l in range(2, n + 1):\n",
    "            for i in range(n - l + 1):\n",
    "                j = i + l - 1\n",
    "               \n",
    "                dp[i][j] = max(f[j + 1] - f[i + 1] - dp[i + 1][j], f[j] - f[i] - dp[i][j - 1])\n",
    "        return dp[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        pres = list(accumulate(stones, initial=0))\n",
    "        # @cache\n",
    "        # def dfs(l, r):\n",
    "        #     if l > r:\n",
    "        #         return 0\n",
    "        #     res = -inf\n",
    "        #     res = max(res, pres[r + 1] - pres[l + 1] - dfs(l + 1, r))\n",
    "        #     res = max(res, pres[r] - pres[l] - dfs(l, r - 1)) \n",
    "        #     return res    \n",
    "        # return dfs(0, n - 1)\n",
    "\n",
    "        dp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                dp[i][j] = max(pres[j] - pres[i + 1] - dp[i + 1][j], pres[j - 1] - pres[i] - dp[i][j - 1])\n",
    "\n",
    "        return dp[0][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        pres = list(accumulate(stones, initial = 0))\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for L in range(2, n + 1):\n",
    "            for i in range(n - L + 1):\n",
    "                j = i + L - 1\n",
    "                dp[i][j] = max(pres[j + 1] - pres[i + 1] - dp[i + 1][j], pres[j] - pres[i] - dp[i][j - 1])\n",
    "        return dp[0][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        pre_sum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            pre_sum[i+1] = pre_sum[i] + stones[i]\n",
    "        \n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                dp[i][j] = max(pre_sum[j+1] - pre_sum[i+1] - dp[i+1][j], pre_sum[j] - pre_sum[i] - dp[i][j-1])\n",
    "        \n",
    "\n",
    "        return dp[0][-1]\n",
    "\n",
    "            \n",
    "            \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        s = list(accumulate(stones, initial=0))\n",
    "        n = len(stones)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            for j in range(n):\n",
    "                k = j + i\n",
    "                if k >= n: break\n",
    "                if j + 1 < n:\n",
    "                    dp[j][k] = max(dp[j][k], s[k + 1] - s[j + 1] - dp[j + 1][k])\n",
    "                if k - 1 >= 0:\n",
    "                    dp[j][k] = max(dp[j][k], s[k] - s[j] - dp[j][k - 1])\n",
    "        return dp[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        pre = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            pre[i + 1] = pre[i] + stones[i]\n",
    "\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                dp[i][j] = max(pre[j + 1] - pre[i + 1] - dp[i + 1]\n",
    "                               [j], pre[j] - pre[i] - dp[i][j - 1])\n",
    "        return dp[0][n - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        # 先手对后手的净胜分\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i>j:return 0\n",
    "        #     return max(presum[j+1]-presum[i]-stones[i]-dfs(i+1,j),presum[j+1]-presum[i]-stones[j]-dfs(i,j-1))\n",
    "        # presum=list(itertools.accumulate(stones,initial=0))\n",
    "        # n=len(stones)\n",
    "        # res=dfs(0,n-1)\n",
    "        # dfs.cache_clear()\n",
    "        # return res\n",
    "        presum=list(itertools.accumulate(stones,initial=0))\n",
    "        n=len(stones)\n",
    "        f=[[0]*n for _ in range(n)]\n",
    "        # print(f)\n",
    "        # f[i][j]=max(presum[j+1]-presum[i]-stones[i]-f[i+1][j],presum[j+1]-presum[i]-stones[j]-f[i][j-1])\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i,n):\n",
    "                if i==j:\n",
    "                    f[i][j]=0\n",
    "                else:\n",
    "                    f[i][j]=max(presum[j+1]-presum[i]-stones[i]-f[i+1][j],presum[j+1]-presum[i]-stones[j]-f[i][j-1])\n",
    "        return f[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        length = len(stones)\n",
    "        dp = [[0] * length for _ in range(length)]\n",
    "        pre = [0]\n",
    "        for v in stones:\n",
    "            pre.append(pre[-1] + v)\n",
    "        for j in range(1,length):\n",
    "            for i in range(j - 1, -1, -1):\n",
    "                dp[i][j] = max(pre[j + 1] - pre[i + 1] - dp[i + 1][j], pre[j] - pre[i] - dp[i][j-1])\n",
    "        return dp[0][length - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        # 初始化 dp 数组\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        # 初始化前缀和数组\n",
    "        prefix_sum = [0]\n",
    "        for stone in stones:\n",
    "            prefix_sum.append(prefix_sum[-1] + stone)\n",
    "        \n",
    "        for length in range(2, n + 1):  # 从小到大考虑所有子数组的长度\n",
    "            for i in range(n - length + 1):  # 计算起始索引\n",
    "                j = i + length - 1  # 计算结束索引\n",
    "                \n",
    "                # 计算子数组 stones[i:j+1] 的和\n",
    "                total = prefix_sum[j + 1] - prefix_sum[i]\n",
    "                \n",
    "                # 选择一个最优方案\n",
    "                dp[i][j] = max(\n",
    "                    total - stones[i] - dp[i+1][j],\n",
    "                    total - stones[j] - dp[i][j-1]\n",
    "                )\n",
    "        \n",
    "        return dp[0][-1]\n",
    "\n",
    "# 测试代码\n",
    "sol = Solution()\n",
    "print(sol.stoneGameVII([5,3,1,4,2]))  # 输出应为 6\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n=len(stones)\n",
    "        if n==1:\n",
    "            return stones[0]\n",
    "        if n==2:\n",
    "            return max(stones)-min(stones)\n",
    "        dp=[[0 for _ in range(n)]for _ in range(n)]\n",
    "        pre=[0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1]=pre[i]+stones[i]\n",
    "            #dp[i][i]=stones[i]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                dp[i][j]=max(pre[j+1]-pre[i+1]-dp[i+1][j],pre[j]-pre[i]-dp[i][j-1])\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        presum = [0]\n",
    "        for num in stones:\n",
    "            presum.append(presum[-1] + num)\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(n-i):\n",
    "                dp[j][i+j] = max(presum[i+j+1]-presum[j+1]-dp[j+1][i+j], presum[i+j]-presum[j]-dp[j][i+j-1])\n",
    "        return dp[0][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "memo = [[0] * (1001) for _ in range(1001)]\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        pres = list(accumulate(stones, initial=0))\n",
    "        \n",
    "        def query(i, j):\n",
    "            return pres[j + 1] - pres[i]\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                memo[i][j] = inf\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if memo[i][j] != inf:\n",
    "                return memo[i][j]\n",
    "            cur = (i + n - 1 - j) & 1\n",
    "            # 极大\n",
    "            if cur == 0:\n",
    "                memo[i][j] = max(dfs(i + 1, j) + query(i + 1, j), dfs(i, j - 1) + query(i, j - 1))\n",
    "                return memo[i][j]\n",
    "            else:\n",
    "                memo[i][j] = min(dfs(i + 1, j) - query(i + 1, j), dfs(i, j - 1) - query(i, j - 1))\n",
    "                return memo[i][j]\n",
    "        \n",
    "        return abs(dfs(0, n - 1))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        if n & 1:\n",
    "            dp = [{} for _ in range(n)]\n",
    "            for i, dic in enumerate(dp):\n",
    "                dic[i] = 0\n",
    "            for i in range(2, n, 2):\n",
    "                for j in range(n-i):\n",
    "                    dp[j][j+i] = max(min(stones[j+1]+dp[j+2][j+i], stones[j+i]+dp[j+1][j+i-1]), min(stones[j]+dp[j+1][j+i-1], stones[j+i-1]+dp[j][j+i-2]))\n",
    "        else:\n",
    "            dp = [{} for _ in range(n-1)]\n",
    "            for i, dic in enumerate(dp):\n",
    "                dic[i+1] = max(stones[i], stones[i+1])\n",
    "            for i in range(3, n, 2):\n",
    "                for j in range(n-i):\n",
    "                    dp[j][j+i] = max(min(stones[j+1]+dp[j+2][j+i], stones[j+i]+dp[j+1][j+i-1]), min(stones[j]+dp[j+1][j+i-1], stones[j+i-1]+dp[j][j+i-2]))\n",
    "        return dp[0][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "sys.setrecursionlimit(10**7)\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        pre_sum = [0 for _ in range(len(stones) + 1)]\n",
    "\n",
    "        for i in range(len(stones)):\n",
    "            pre_sum[i + 1] = pre_sum[i] + stones[i]\n",
    "        \n",
    "        #dp[i][j] = max(pre_sum[j + 1] - pre_sum[i] - dp[i + 1][j],  )\n",
    "        #.              pre_sum[j ] - pre_sum[i + 1] - dp[i ][j - 1]\n",
    "\n",
    "        dp = [[float('-inf') for _ in range(len(stones))] for _ in range(len(stones))]\n",
    "        for i in range(len(stones) - 1, -1, -1):\n",
    "            for j in range(i, len(stones)):\n",
    "                if i == j:\n",
    "                    dp[i][j] = max(dp[i][j],0)\n",
    "                else:\n",
    "                    dp[i][j] = max(pre_sum[j + 1] - pre_sum[i + 1] - dp[i + 1][j], pre_sum[j ] - pre_sum[i] - dp[i][j - 1])\n",
    "        \n",
    "        return dp[0][len(stones) - 1]\n",
    "\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(left, right, status):\n",
    "            if left >= right:\n",
    "                return 0\n",
    "\n",
    "            if status == 0:\n",
    "                left_ans = pre_sum[right + 1] - pre_sum[left + 1] + dfs(left + 1, right, 1)\n",
    "                right_ans = pre_sum[right ] - pre_sum[left ] + dfs(left, right - 1, 1)\n",
    "                return max(left_ans, right_ans)\n",
    "            else:\n",
    "                left_ans = -(pre_sum[right + 1] - pre_sum[left + 1]) + dfs(left + 1, right, 0)\n",
    "                right_ans = -(pre_sum[right ] - pre_sum[left ]) + dfs(left, right - 1, 0)\n",
    "                return min(left_ans, right_ans)\n",
    "        \n",
    "        return dfs(0, len(stones) - 1, 0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        length = len(stones)\n",
    "        sum_matrix = [[0 for _ in range(length)] for _ in range(length)]\n",
    "        for i in range(length):\n",
    "            sum_matrix[i][i] = stones[i]\n",
    "            for j in range(i+1, length):\n",
    "                sum_matrix[i][j] = stones[j] + sum_matrix[i][j-1]\n",
    "        dp = [[0 for _ in range(length)] for _ in range(length)]\n",
    "        for i in range(length-1, -1, -1):\n",
    "            for j in range(length):\n",
    "                if i == j:\n",
    "                    dp[i][j] = 0\n",
    "                elif j - i == 1:\n",
    "                    dp[i][j] = max(stones[i:j+1])\n",
    "                elif j - i > 1:\n",
    "                    dp[i][j] = max(sum_matrix[i+1][j] - dp[i+1][j], \n",
    "                                sum_matrix[i][j-1] - dp[i][j-1])\n",
    "        return dp[0][length-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "\n",
    "        flag = (n - 1) % 2\n",
    "        seen = dict()\n",
    "        # @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i >= j: return 0\n",
    "            if (i+2,j) not in seen:\n",
    "                seen[i+2,j] = dfs(i+2,j)\n",
    "            if (i+1,j-1) not in seen:\n",
    "                seen[i+1,j-1] = dfs(i+1,j-1)\n",
    "            if (i,j-2) not in seen:\n",
    "                seen[i,j-2] = dfs(i,j-2)\n",
    "            if (i + j) % 2 == flag:\n",
    "                return max(\n",
    "                    min(seen[i + 2, j] + stones[i + 1], seen[i + 1, j - 1] + stones[j]),\n",
    "                    min(seen[i, j - 2] + stones[j - 1], seen[i + 1, j - 1] + stones[i])\n",
    "                )\n",
    "            else:\n",
    "                return min(\n",
    "                    max(seen[i + 2, j] - stones[i + 1], seen[i + 1, j - 1] - stones[j]),\n",
    "                    max(seen[i, j - 2] - stones[j - 1], seen[i + 1, j - 1] - stones[i])\n",
    "                )\n",
    "        ans = dfs(0, n - 1)\n",
    "        del seen\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "\n",
    "        # flag = (n - 1) % 2\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i >= j: return 0\n",
    "            # if (i + j) % 2 == flag:\n",
    "            return max(\n",
    "                min(dfs(i + 2, j) + stones[i + 1], dfs(i + 1, j - 1) + stones[j]),\n",
    "                min(dfs(i, j - 2) + stones[j - 1], dfs(i + 1, j - 1) + stones[i])\n",
    "            )\n",
    "            # else:\n",
    "            #     return min(\n",
    "            #         max(dfs(i + 2, j) - stones[i + 1], dfs(i + 1, j - 1) - stones[j]),\n",
    "            #         max(dfs(i, j - 2) - stones[j - 1], dfs(i + 1, j - 1) - stones[i])\n",
    "            #     )\n",
    "        ans = dfs(0, n - 1)\n",
    "        # print(dfs.cache_info())\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "\n",
    "        flag = (n - 1) % 2\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i >= j: return 0\n",
    "            # if (i + j) % 2 == flag:\n",
    "            return max(\n",
    "                min(dfs(i + 2, j) + stones[i + 1], dfs(i + 1, j - 1) + stones[j]),\n",
    "                min(dfs(i, j - 2) + stones[j - 1], dfs(i + 1, j - 1) + stones[i])\n",
    "            )\n",
    "            # else:\n",
    "            #     return min(\n",
    "            #         max(dfs(i + 2, j) - stones[i + 1], dfs(i + 1, j - 1) - stones[j]),\n",
    "            #         max(dfs(i, j - 2) - stones[j - 1], dfs(i + 1, j - 1) - stones[i])\n",
    "            #     )\n",
    "        ans = dfs(0, n - 1)\n",
    "        # print(dfs.cache_info())\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "\n",
    "        flag = (n - 1) % 2\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i >= j: return 0\n",
    "            if (i + j) % 2 == flag:\n",
    "                return max(\n",
    "                    min(dfs(i + 2, j) + stones[i + 1], dfs(i + 1, j - 1) + stones[j]),\n",
    "                    min(dfs(i, j - 2) + stones[j - 1], dfs(i + 1, j - 1) + stones[i])\n",
    "                )\n",
    "            else:\n",
    "                return min(\n",
    "                    max(dfs(i + 2, j) - stones[i + 1], dfs(i + 1, j - 1) - stones[j]),\n",
    "                    max(dfs(i, j - 2) - stones[j - 1], dfs(i + 1, j - 1) - stones[i])\n",
    "                )\n",
    "        ans = dfs(0, n - 1)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n",
    "        # return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        add_sum = list(accumulate(stones, initial=0))\n",
    "        dp = [[[0]*2 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i][0], dp[i][i][1] = 0, 0\n",
    "        for L in range(2, n+1):\n",
    "            for i in range(0, n-L+1):\n",
    "                l,r = i,i+L-1\n",
    "                ld = dp[l+1][r][1] + add_sum[r+1]-add_sum[l+1] - dp[l+1][r][0]\n",
    "                rd = dp[l][r-1][1] + add_sum[r]-add_sum[l] - dp[l][r-1][0]\n",
    "                if ld>rd:\n",
    "                    dp[l][r][0],dp[l][r][1] = dp[l+1][r][1] + add_sum[r+1]-add_sum[l+1],dp[l+1][r][0]\n",
    "                else:\n",
    "                    dp[l][r][0],dp[l][r][1] = dp[l][r-1][1] + add_sum[r]-add_sum[l], dp[l][r-1][0]\n",
    "                    \n",
    "        return dp[0][n-1][0] - dp[0][n-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        # 区间DP，判断的条件与石子游戏877不同的是，877是让先手者石子更多\n",
    "        # 这题是让先手者与后手者的差距更大\n",
    "        n = len(stones)\n",
    "        add_sum = list(accumulate(stones, initial=0))\n",
    "        dp = [[[0]*2 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i][0], dp[i][i][1] = 0, 0\n",
    "        for L in range(2, n+1):\n",
    "            for i in range(0, n-L+1):\n",
    "                l,r = i,i+L-1\n",
    "                ld = dp[l+1][r][1] + add_sum[r+1]-add_sum[l+1] - dp[l+1][r][0]\n",
    "                rd = dp[l][r-1][1] + add_sum[r]-add_sum[l] - dp[l][r-1][0]\n",
    "                if ld>rd:\n",
    "                    dp[l][r][0],dp[l][r][1] = dp[l+1][r][1] + add_sum[r+1]-add_sum[l+1],dp[l+1][r][0]\n",
    "                else:\n",
    "                    dp[l][r][0],dp[l][r][1] = dp[l][r-1][1] + add_sum[r]-add_sum[l], dp[l][r-1][0]\n",
    "                    \n",
    "        return dp[0][n-1][0] - dp[0][n-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        s = list(accumulate(stones, initial=0))\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == j:\n",
    "                return 0\n",
    "            return max(s[j + 1] - s[i + 1] - dfs(i + 1, j), s[j] - s[i] - dfs(i, j - 1))\n",
    "        res = dfs(0, len(stones) - 1)\n",
    "        del dfs\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def stoneGameVII(self, stones: List[int]) -> int:\n",
    "#         pre = list(accumulate(stones))\n",
    "#         ans = 0\n",
    "#         @lru_cache(None)\n",
    "#         def dfs(l,r,flag):   \n",
    "#             nonlocal ans         \n",
    "#             if l >= r:\n",
    "#                 return 0\n",
    "#             lnum,rnum = pre[r-1]-(pre[l-1] if l!=0 else 0), pre[r]-pre[l]\n",
    "#             if flag:\n",
    "#                 if lnum > rnum:\n",
    "#                     ans += lnum\n",
    "#                     dfs(l,r-1)\n",
    "#                 elif lnum < rnum:\n",
    "#                     ans += rnum\n",
    "#                     dfs(l+1,r)\n",
    "#                 else:\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        pre = list(accumulate(stones,initial=0))\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i >= j: return 0\n",
    "            return max(pre[j + 1] - pre[i + 1] - dfs(i + 1, j), pre[j] - pre[i] - dfs(i, j - 1))\n",
    "        res = dfs(0, len(stones) - 1)\n",
    "        dfs.cache_clear()\n",
    "        return res        \n",
    "            \n",
    "        \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        s = list(accumulate(stones, initial=0))\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == j:\n",
    "                return 0\n",
    "            return max(s[j + 1] - s[i + 1] - dfs(i + 1, j), s[j] - s[i] - dfs(i, j - 1))\n",
    "        res = dfs(0, len(stones) - 1)\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        s = [0] * n\n",
    "        for i, x in enumerate(stones):\n",
    "            s[i] = x + (s[i - 1] if i > 0 else 0)\n",
    "        # print(f's:{s}')\n",
    "        def val(i: int, j: int) -> int:\n",
    "            return s[j] - (s[i - 1] if i > 0 else 0)\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, a: bool) -> int:\n",
    "            if i == j:\n",
    "                # print(f'i:{i},j:{j},a:{a}')\n",
    "                return 0\n",
    "            if a:\n",
    "                ans = max(dfs(i + 1, j, False) + val(i + 1, j), dfs(i, j - 1, False) + val(i, j - 1))\n",
    "                # print(f'ans:{ans},i:{i},j:{j},a:{a}')\n",
    "                return ans\n",
    "            else:\n",
    "                ans = min(dfs(i + 1, j, True) - val(i + 1, j), dfs(i, j - 1, True) - val(i, j - 1))\n",
    "                # print(f'ans:{ans},i:{i},j:{j},a:{a}')\n",
    "                return ans\n",
    "        ans = dfs(0, n - 1, True)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        pre_sum = list(accumulate(stones, initial=0))\n",
    "        # 区间DP\n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            if l >= r: # 只有一个元素，移除之后，没有剩余的石子，没有得分，差值也是0\n",
    "                return 0\n",
    "            # 移除l,得分为[l+1..r]的和\n",
    "            # 移除r,得分为[l..r-1]的和\n",
    "            res1 = pre_sum[r+1] - pre_sum[l+1] - dfs(l+1, r) # 两位玩家的得分差值\n",
    "            res2 = pre_sum[r] - pre_sum[l] - dfs(l, r-1) \n",
    "            return max(res1, res2)\n",
    "        res = dfs(0, len(stones) - 1)\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "\n",
    "        n = len(stones)\n",
    "        pre = list(accumulate(stones, initial=0))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i == j:\n",
    "                return 0\n",
    "            return max(-dfs(i+1, j) + pre[j+1]-pre[i+1], -dfs(i, j-1)+pre[j]-pre[i])\n",
    "        ans =  dfs(0, n-1)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "\n",
    "        s = list(accumulate(stones, initial=0))\n",
    "        @cache \n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i == j:\n",
    "                return 0\n",
    "            return max(s[j + 1] - s[i + 1] - dfs(i + 1, j), s[j] - s[i] - dfs(i, j - 1))\n",
    "\n",
    "        res = dfs(0, len(stones) - 1)\n",
    "        dfs.cache_clear()\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        s = [0] * n\n",
    "        for i, x in enumerate(stones):\n",
    "            s[i] = x + (s[i - 1] if i > 0 else 0)\n",
    "        # print(f's:{s}')\n",
    "        def val(i: int, j: int) -> int:\n",
    "            return s[j] - (s[i - 1] if i > 0 else 0)\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i == j:\n",
    "                # print(f'i:{i},j:{j},a:{a}')\n",
    "                return 0\n",
    "            return max(val(i + 1, j) - dfs(i + 1, j), val(i, j - 1) - dfs(i, j - 1))\n",
    "        ans = dfs(0, n - 1)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def stoneGameVII(self, stones: List[int]) -> int:\n",
    "#         pre = list(accumulate(stones))\n",
    "#         ans = 0\n",
    "#         @lru_cache(None)\n",
    "#         def dfs(l,r,flag):   \n",
    "#             nonlocal ans         \n",
    "#             if l >= r:\n",
    "#                 return 0\n",
    "#             lnum,rnum = pre[r-1]-(pre[l-1] if l!=0 else 0), pre[r]-pre[l]\n",
    "#             if flag:\n",
    "#                 if lnum > rnum:\n",
    "#                     ans += lnum\n",
    "#                     dfs(l,r-1)\n",
    "#                 elif lnum < rnum:\n",
    "#                     ans += rnum\n",
    "#                     dfs(l+1,r)\n",
    "#                 else:\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        # pre = [0]\n",
    "        # for s in stones:\n",
    "        #     pre.append(pre[-1] + s)\n",
    "        pre = list(accumulate(stones,initial=0))\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j: return 0\n",
    "            return max(pre[j + 1] - pre[i + 1] - dfs(i + 1, j), pre[j] - pre[i] - dfs(i, j - 1))\n",
    "        res = dfs(0, len(stones) - 1)\n",
    "        dfs.cache_clear()\n",
    "        return res        \n",
    "            \n",
    "        \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def stoneGameVII(self, stones: List[int]) -> int:\n",
    "#         pre = list(accumulate(stones))\n",
    "#         ans = 0\n",
    "#         @lru_cache(None)\n",
    "#         def dfs(l,r,flag):   \n",
    "#             nonlocal ans         \n",
    "#             if l >= r:\n",
    "#                 return 0\n",
    "#             lnum,rnum = pre[r-1]-(pre[l-1] if l!=0 else 0), pre[r]-pre[l]\n",
    "#             if flag:\n",
    "#                 if lnum > rnum:\n",
    "#                     ans += lnum\n",
    "#                     dfs(l,r-1)\n",
    "#                 elif lnum < rnum:\n",
    "#                     ans += rnum\n",
    "#                     dfs(l+1,r)\n",
    "#                 else:\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        pre = [0]\n",
    "        for s in stones:\n",
    "            pre.append(pre[-1] + s)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j: return 0\n",
    "            return max(pre[j + 1] - pre[i + 1] - dfs(i + 1, j), pre[j] - pre[i] - dfs(i, j - 1))\n",
    "        res = dfs(0, len(stones) - 1)\n",
    "        dfs.cache_clear()\n",
    "        return res        \n",
    "            \n",
    "        \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        pre_sum = [0]\n",
    "        for x in stones:\n",
    "            pre_sum.append(x + pre_sum[-1])\n",
    "        print(pre_sum)\n",
    "        @cache\n",
    "        def dfs(l:int, r:int):\n",
    "            if l == r:\n",
    "                return 0\n",
    "            return max(pre_sum[r+1] - pre_sum[l+1] - dfs(l+1, r), pre_sum[r] - pre_sum[l] - dfs(l, r-1))\n",
    "        res = dfs(0, n-1)\n",
    "        dfs.cache_clear()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def stoneGameVII(self, stones: List[int]) -> int:\n",
    "#         pre = list(accumulate(stones))\n",
    "#         ans = 0\n",
    "#         @lru_cache(None)\n",
    "#         def dfs(l,r,flag):   \n",
    "#             nonlocal ans         \n",
    "#             if l >= r:\n",
    "#                 return 0\n",
    "#             lnum,rnum = pre[r-1]-(pre[l-1] if l!=0 else 0), pre[r]-pre[l]\n",
    "#             if flag:\n",
    "#                 if lnum > rnum:\n",
    "#                     ans += lnum\n",
    "#                     dfs(l,r-1)\n",
    "#                 elif lnum < rnum:\n",
    "#                     ans += rnum\n",
    "#                     dfs(l+1,r)\n",
    "#                 else:\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        pre = [0]\n",
    "        for s in stones:\n",
    "            pre.append(pre[-1] + s)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j: return 0\n",
    "            return max(pre[j + 1] - pre[i + 1] - dfs(i + 1, j), pre[j] - pre[i] - dfs(i, j - 1))\n",
    "        res = dfs(0, len(stones) - 1)\n",
    "        dfs.cache_clear()\n",
    "        return res        \n",
    "            \n",
    "        \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        # 先手对后手的净胜分\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i>j:return 0\n",
    "            return max(presum[j+1]-presum[i]-stones[i]-dfs(i+1,j),presum[j+1]-presum[i]-stones[j]-dfs(i,j-1))\n",
    "        presum=list(itertools.accumulate(stones,initial=0))\n",
    "        n=len(stones)\n",
    "        res=dfs(0,n-1)\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        pre = [0]\n",
    "        for stone in stones:\n",
    "            pre.append(pre[-1] + stone)\n",
    "        dp = [[inf] * (n+1) for _ in range(n+1)]\n",
    "\n",
    "        def dfs(l:int,r:int)->int:\n",
    "            if l == r:\n",
    "                dp[l][r] = 0\n",
    "                return 0\n",
    "            if dp[l][r] != inf:\n",
    "                return dp[l][r]\n",
    "            r1 = -dfs(l+1,r) + pre[r] - pre[l]\n",
    "            r2 = -dfs(l,r-1) + pre[r-1] - pre[l-1]\n",
    "            dp[l][r] = max(r1,r2)\n",
    "            return dp[l][r]\n",
    "        return dfs(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\r\n",
    "        n = len(stones)\r\n",
    "        s = list(accumulate(stones, initial=0))\r\n",
    "        memo = [[-1] * (n + 1) for _ in range(n + 1)]\r\n",
    "        def dfs(i: int, j: int) -> int:\r\n",
    "            if i == j:\r\n",
    "                return 0\r\n",
    "            if memo[i][j] != -1:\r\n",
    "                return memo[i][j]\r\n",
    "            memo[i][j] = max(s[j + 1] - s[i + 1] - dfs(i + 1, j), s[j] - s[i] - dfs(i, j - 1))\r\n",
    "            return memo[i][j]\r\n",
    "        return dfs(0, len(stones) - 1)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        @lru_cache(maxsize = 1200000)\n",
    "        def dfs(l, r, score):\n",
    "            if l == r: return 0\n",
    "            return max(score - stones[l] - dfs(l + 1, r, score - stones[l]), score - stones[r] - dfs(l, r - 1, score - stones[r]))\n",
    "        ret = dfs(0, len(stones) - 1, sum(stones))\n",
    "        dfs.cache_clear()\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        s = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            s[i][i] = stones[i]\n",
    "            for j in range(i + 1, n):\n",
    "                s[i][j] = s[i][j - 1] + stones[j]\n",
    "        @cache\n",
    "        def dp(left, right):\n",
    "            if left == right:\n",
    "                return 0\n",
    "            return max(s[left + 1][right] - dp(left + 1, right), s[left][right - 1] - dp(left, right - 1))\n",
    "        return dp(0, n - 1)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
